//
// Created by liugang on 9/12/25.
//

#ifndef LIST_HEAD_H
#define LIST_HEAD_H

#ifndef NDEBUG
#include <cassert>
#define ASSERT(expr) assert(expr)
#else
#define ASSERT(expr)
#endif//NDEBUG

#include <cstddef>

struct list_head {
    list_head* next;
    list_head* prev;

    explicit list_head() {
        next = this;
        prev = this;
    }
};

template <typename T>
inline auto list_head_init(T* head) -> T* {
    ASSERT(head != nullptr);
    head->next = head;
    head->prev = head;
    return head;
}

template <typename T>
inline auto list_empty(T* head) -> bool {
    ASSERT(head != nullptr);
    return head->next == head;
}

template <typename T>
inline auto list_end(T* head) -> T* {
    return head;
}

template <typename T>
inline auto list_end(const T* head) -> const T* {
    return head;
}

template <typename T>
inline auto list_front(T* head) -> T* {
    return head->next;
}

template <typename T>
inline auto list_front(const T* head) -> const T* {
    return head->next;
}

template <typename T>
inline auto list_back(T* head) -> T* {
    return head->prev;
}

template <typename T>
inline auto list_back(const T* head) -> const T* {
    return head->prev;
}

template <typename T>
inline auto list_insert(T* prev, T* next, T* elem) -> void {
    ASSERT(prev != nullptr);
    ASSERT(next != nullptr);
    ASSERT(elem != nullptr);
    elem->next = next;
    elem->prev = prev;
    prev->next = elem;
    next->prev = elem;
}

template <typename T>
inline auto list_remove(T* prev, T* next) -> void {
    ASSERT(prev != nullptr);
    ASSERT(next != nullptr);
    prev->next = next;
    next->prev = prev;
}

template <typename T>
inline auto list_split(T* elem) -> T* {
    ASSERT(elem != nullptr);
    list_remove(elem->prev, elem->next);
    return list_head_init(elem);
}

template <typename T>
inline auto list_append(T* head, T* elem) -> void {
    ASSERT(head != nullptr);
    ASSERT(elem != nullptr);
    list_insert(head->prev, head, elem);
    ASSERT((head->next == list_end(head)) ? (head->prev == list_end(head)) : true);
}

template <typename T>
inline auto list_pop_back(T* head) -> T* {
    if (head->prev == list_end(head)) {
        return nullptr;
    }

    return list_split(head->prev);
}

template <typename T>
inline auto list_pop_front(T* head) -> T* {
    if (head->next == list_end(head)) {
        return nullptr;
    }

    return list_split(head->next);
}

template <typename T>
inline auto list_prepend(T* head, T* elem) -> void {
    ASSERT(head != nullptr);
    ASSERT(elem != nullptr);
    list_insert(head, head->next, elem);
    ASSERT((head->next == list_end(head)) ? (head->prev == list_end(head)) : true);
}

template <typename T>
inline auto list_swap(T* head, T* other) -> const T* {
    auto tmp = head;
    *head = *other;
    *other = tmp;
    head->next->prev = head;
    head->prev->next = head;
    other->next->prev = other;
    other->prev->next = other;
    ASSERT((head->next == list_end(head)) ? (head->prev == list_end(head)) : true);
}


template <typename T>
inline auto list_child(T* head, size_t index) -> T* {
    ASSERT(head != nullptr);
    if (list_empty(head)) {
        return nullptr;
    }

    auto item = list_front(head);
    while (index > 0) {
        item = item->next;
        if (item == head) {
            return nullptr;
        }

        --index;
    }

    return item;
}


#define LIST_FOREACH(elem, head) \
    for (auto elem = (head)->next; elem != list_end(head); elem = elem->next)

#define LIST_FOREACH_SAVE(elem, n, head) \
    for (auto elem = (head)->next, n = elem->next; elem != list_end(head); elem = n, n = n->next)


#endif //LIST_HEAD_H
